package cn.rocky.prepare;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Stack;

/**
 * 946. 验证栈序列
 * 给定 pushed 和 popped 两个序列，
 * 每个序列中的 值都不重复，
 * 只有当它们可能是在最初空栈上进行的推入 push 和
 * 弹出 pop 操作序列的结果时，返回 true；
 * 否则，返回 false。
 **/
public class validateStackSequences {

    public static void main(String[] args) {
        int[] pushed = new int[]{1,2,3,4,5};
        int[] popped = new int[]{4,5,3,2,1};
        System.out.println(validateStackSequences(pushed, popped));
    }

    public static boolean validateStackSequences(int[] pushed, int[] popped) {
        if (pushed.length != popped.length) {return false;}
        Deque<Integer> stack = new ArrayDeque<>();
        int n = pushed.length;
        for (int i = 0,j = 0; i < n; i++) {
            stack.push(pushed[i]);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}
